package leetCode.solution;

public class Solution421 {
	Trie root = new Trie();
	static final int HIGH_BIT = 30;

	public int findMaximumXOR(int[] nums) {
		int n = nums.length;
        int x = 0;
        for(int i = 0;i<n-1;i++) {
        	add(nums[i]);
        	x = Math.max(x, check(nums[i+1]));
        }
        return x;
	}

	public void add(int num) {
		Trie cur = root;
		for (int i = HIGH_BIT; i >= 0; i--) {
			int bit = (num >> i) & 1;
			if (bit == 0) {
				if (cur.left == null) {
					cur.left = new Trie();
				}
				cur = cur.left;
			} else {
				if (cur.right == null) {
					cur.right = new Trie();
				}
				cur = cur.right;
			}
		}
	}
	public int check(int num) {
		int x = 0;
		Trie cur = root;
		for (int i = HIGH_BIT; i >= 0; i--) {
			int bit = (num >> i) & 1;
			if (bit == 0) {
                // a_i 的第 k 个二进制位为 0，应当往表示 1 的子节点 right 走
                if (cur.right != null) {
                    cur = cur.right;
                    x = x * 2 + 1;
                } else {
                    cur = cur.left;
                    x = x * 2;
                }
            } else {
                // a_i 的第 k 个二进制位为 1，应当往表示 0 的子节点 left 走
                if (cur.left != null) {
                    cur = cur.left;
                    x = x * 2 + 1;
                } else {
                    cur = cur.right;
                    x = x * 2;
                }
            }
		}
		return x;
	}

	class Trie { // 比数组效率高
		Trie left = null;
		Trie right = null;
	}
	
//	Node root = new Node();
//
//	public int findMaximumXOR(int[] nums) {
//		int n = nums.length;
//		int x = 0;
//		add(nums[0]);
//		for (int i = 1; i < n; i++) {
//			x = Math.max(x, check(nums[i]));
//			add(nums[i]);
//		}
//		return x;
//	}
//
//	public void add(int num) {
//		Node cur = root;
//		for (int i = 31; i >= 0; i--) {
//			int bit = (num >> i) & 1;
//			cur.nexts[bit] = cur.nexts[bit] == null ? new Node() : cur.nexts[bit];
//			cur = cur.nexts[bit];
//		}
//	}
//
//	public int check(int num) {
//		int x = 0;
//		Node cur = root;
//		for (int i = 31; i >= 0; i--) {
//			int bit = (num >> i) & 1;
//			int best = i == 31 ? bit : (bit ^ 1);
//			best = cur.nexts[best] == null ? best ^ 1 : best;
//			x |= (bit ^ best) << i;
//			cur = cur.nexts[best];
//		}
//		return x;
//	}
//
//	class Node {
//		Node[] nexts = new Node[2];
//	}
}
